CS 235 Spring 2008 Final Exam Information Dates: Wednesday, June 18, 1:00 p.m. to 2:50 p.m. Place: Classroom where we normally meet Closed book 1-page notes (both sides) 2 hour time limit No calculator Although focusing on the second part of the course, the final exam is comprehensive as many topics introduced in the first part are fundamental and have been used throughout (e.g., recursion, iterators, bigOh, etc.). As a result, you will find that some questions are based on material covered in the midterm. Topics covered in the final exam are as follows: Chapter 5 * Logarithms: Understand the definition of a logarithm in any base, know that Log(a*b) = Log(a) + Log(b), know how to apply logarithms to basic problems in computer science, such as determining how many bits are needed to represent a binary number, or knowing how many times a number can be cut in half before the answer is <=1. * Given a code fragment, determine the big-oh running time. * Given an algorithm that takes time t on size n, determine the time on size k. * Given an algorithm that takes time t on size n, determine the size in time r. * Given a table of empirical results with size and time, determine the big-oh function that best describes the time. * Given a list of big-oh functions in an arbitrary order, sort the functions in order of growth. * Given an array of values and an item x to search for, determine the part of the array in which x could still be found after each major step of binary search. Chapter 6 * Know what an Iterator is and what its operations do. * Know the behavior of each standard operation for each data type: * list (get, set, add, remove, contains) * stack (push, pop, top) * queue (enqueue, dequeue, getFront) * set (add, remove, contains) * map (get, put, remove, containsKey) * priority queue (insert, findMin, deleteMin) Chapter 7 * First two fundamental rules of recursion: base case, make progress. * Examples: Merge sort, quick sort, Fibonacci, print numbers in any base * Recursive run time functions Chapter 8 * Determine the content of an array after each major step of insertion sort. * Determine the content of an array after each major step of selection sort. * Determine the content of an array in the middle of mergesort after the two recursive calls to mergesort have completed but before the call to merge. * Determine the content of an array in the middle of quicksort after the array has been partitioned but before the two recursive calls to quicksort. * Know the average case, worst case, and best case big-oh for the following algorithms: selection sort, merge sort, insertion sort, quick sort, quick select, binary search Chapter 15 * How are add/remove/find/set/get implemented on an array list? * What happens when the array in an array list becomes full? * How do you implement an iterator on an array list? * What's the Big-Oh for add/remove/find/set/get on an array list? Chapter 16 * How are push/pop implemented on an array stack? * How are push/pop implemented on a linked-list stack? * How are enqueue/dequeue implemented on an array queue? * How are enqueue/dequeue implemented on a linked-list queue? * What's the Big-Oh for push/pop/enqueue/dequeue? Chapter 17 * How are add/remove/find/set/get implemented on a linked list? * How do you implement an iterator on a linked list? * What's the Big-Oh for add/remove/find/set/get on a linked list? * How are links set when inserting/deleting first/middle/last node in single/double linked-list? Chapter 18 * Show how a tree can be represented using first-child/next-sibling. * What's the height/depth of nodes in a tree? * What's the preorder/postorder/inorder listing of nodes in a tree? * How can recursive methods traverse a tree and compute various results? * How do you implement preorder/levelorder iterators on a tree? * How can an arithmetic expression be represented using a tree? Chapter 19 * What's a valid BST based on the order property? * How do you find/add/remove something in a BST? * What's the Big-Oh for add/remove/find on a BST? * What's a valid AVL-BST based on the balance property? * How do you find/add/remove something in an AVL-BST? * What's the Big-Oh for add/remove/find on an AVL-BST? * How do you implement Set/Map using a BST? Chapter 20 * How do you find/add/remove something in a hash table? * What's a good/bad hash function? * How do you resolve collisions using linear/quadratic probing? * How do you resolve collisions using chaining? * What's the Big-Oh for add/remove/find on hash table? * How do you implement Set/Map using a hash table? Chapter 21 * What's a valid heap based on the structure property? * What's a valid heap based on the order property? * How is a heap stored in an array? * How do you insert/findMin/deleteMin on a min heap? * How do you insert/findMax/deleteMax on a max heap? * How does buildHeap make a heap? * How does heapsort sort an array? * What's the Big-Oh for insert/findMin/deleteMin? * What's the Big-Oh for insert/findMax/deleteMax? * What's the Big-Oh for buildHeap/heapsort?